/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> list = new LinkedList<>();
    LinkedList<Integer> arr = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        fun(root,target,0);
        //fun(root,target);
        return list;
    }
    public void fun(TreeNode root, int target,int sum) {
        if(root == null) return;
        arr.add(root.val);
        sum+=root.val;
        //target-=root.val;
        if(sum == target && root.left == null && root.right == null) {
            list.add((new LinkedList<>(arr)));
            //会提前回溯(相等的那个结点没有回溯,一直回溯的是后一个结点)
            arr.remove(arr.size()-1);
            return;
        }
        // if(0 == target && root.left == null && root.right == null) {
        //     list.add((new LinkedList<>(arr)));
        //     arr.remove(arr.size()-1);
        //     return;
        // }
        fun(root.left,target,sum);
        fun(root.right,target,sum);
        // fun(root.left,target);
        // fun(root.right,target);
        arr.removeLast();
    }
}